#ifndef TC_DB_MANAGER_HPP
#define TC_DB_MANAGER_HPP

#define TC_DB_MAX_W 130 // Maximum path loss (used in the weight avg)

#include <boost/graph/adjacency_list.hpp>
#include <string>
#include <list>
#include <map>
#include <iostream>
#include <utility> // for pair<> and make_pair()

using std::string;
using std::pair;
using std::make_pair;
using namespace boost;

//////////////////////////////////////////////////////////
// Graph class used in the database manager
//   using bundled properties to associate information
//   for vertices and edges
//   [http://www.boost.org/libs/graph/doc/bundles.html]

struct Node
{
  string IP;
  string MAC;
  bool TPC;
  int MAX_POWER;
  double Toc; // time-out counter
};

struct Link
{
  double Weight;
  double Toc;
};

typedef boost::adjacency_list<
  boost::listS, boost::listS, boost::bidirectionalS,
  Node, Link> Graph;


// Comparison function for edges (used in MakeSimpleGraph())
struct compare_edge
{
  template <typename Edge>
  bool operator() (const Edge& e1, const Edge& e2)
  {
    return true;
  }
};



//////////////////////////////////////////////////////////
// Topology Database Manager class

class TCDatabaseManager{
public:
  // Default constructor
  TCDatabaseManager()
  {isReady = false; Tic = 0; T = 5.0; T_e = 5.0; N_e = 4; useAvg = true;}

  // Set "use time window averaging" parameter
  void SetUseAvg(bool value) {useAvg = value;}
  
  // Set node time-out value
  void SetTimeOut(double time_out) {T = time_out;}

  // Set edge time-out value (memory size)
  void SetEdgeTimeOut(double time_out) {T_e = time_out;}

  // Set the window size for the calculation of average edge weight
  void SetEdgeWindowSize(int size) {N_e = size;}

  // Check if the graph is ready for use
  bool Ready() {return isReady;}
  
  // Get number of nodes in the graph
  int NumberOfNodes() {return num_vertices(G);}

  // Add a new node or update existing node information (including the timer)
  void AddNode(string ip, string mac, bool tpc, int max_power);

  // Add a new PARALLEL edge (u,v)
  bool AddEdge(string source, string dest);

  // Add a new PARALLEL edge (u,v) including weight parameter
  bool AddEdge(string source, string dest, double weight);

  // Add a set of in_edges towards node u
  // Note that in_edges(u) is first deleted, then reconstructed
  template <typename NeighborList>
  bool AddNeighborhood(string ip, NeighborList& ip_list);

  // Add a set of in_edges towards node u
  // Same as above, but adds the edge weights
  template <typename NeighborList, typename WeightList>
  bool AddNeighborhood(string ip, NeighborList& ip_list, WeightList& w_list);

  // Get the size of the list of neighbors for node u
  int GetNumberOfNeighbors(string ip);

  // Get the size of the list of neighbors for node u (indexed version)
  int GetNumberOfNeighbors(int index);

  // Get the list of neighbors for node u
  template <typename NeighborList>
  bool GetNeighborhood(string ip, NeighborList& ip_list);

  // Get the list of neighbors for node u with the respective in_edge weights
  template <typename NeighborList, typename WeightList>
  bool GetNeighborhood(string ip, NeighborList& ip_list, WeightList& w_list);

  // Get information about node[index]
  bool GetNodeInfo(int index, string& ip, string& mac,
		   bool& tpc, int& max_power);

  // Get information about node indexed by IP address
  bool GetNodeInfo(string source_ip, string& ip, string& mac,
		   bool& tpc, int& max_power);

  // Get graph
  bool GetGraph(Graph& GG);
  
  // Print graph on the standard output
  void PrintGraph();

  // Update timer variable (this function should be called periodically)
  // Note: calling UpdateGraph() too often may cause too much overhead
  void UpdateTimer(double time) {Tic = time; UpdateGraph();}

private:
  Graph G; // main graph object (allows parallel edges)
  bool isReady;
  bool useAvg;
  double T; // Time-out value in seconds
  double T_e; // Time-window (memory) for edge information
  int N_e; // Max. number of parallel edges in weight average calculations
  double Tic; // Final "time" for time-out calculations
  
  // Check graph for completeness (all edges should have weights)
  bool CheckGraph();

  // Makes a simple version of multigraph G (i.e., parallel edges are
  // averaged out into unique edges) and copies it to GG
  void MakeSimpleGraph(Graph& GG);

  // Get reference to node with given IP address
  std::pair<graph_traits<Graph>::vertex_descriptor, bool>
  GetNodeByIP(string ip);

  // Remove node by IP address
  bool RemoveNodeByIP(string ip);

  // Remove node by reference
  void RemoveNode(graph_traits<Graph>::vertex_descriptor v);

  // Remove edge by reference
  void RemoveEdge(graph_traits<Graph>::edge_descriptor e);

  // Reset node timer
  void ResetNodeTimer(graph_traits<Graph>::vertex_descriptor v);

  // Update graph: delete expired nodes and all associated edges
  void UpdateGraph();
};


// --- Member Functions ---

/////////
void TCDatabaseManager::AddNode(string ip, string mac,
			       bool tpc, int max_power)
{
  graph_traits<Graph>::vertex_descriptor v;
  bool exist;

  tie(v, exist) = GetNodeByIP(ip);
  if (!exist){
    v = add_vertex(G);
  }

  G[v].IP = ip;
  G[v].MAC = mac;
  G[v].TPC = tpc;
  G[v].MAX_POWER = max_power;
  G[v].Toc = Tic; // reset timer
}

/////////
bool TCDatabaseManager::AddEdge(string source, string dest)
{
  return AddEdge(source, dest, -1.0);
}

/////////
bool TCDatabaseManager::AddEdge(string source, string dest, double weight)
{
  graph_traits<Graph>::vertex_descriptor u, v;
  graph_traits<Graph>::edge_descriptor e;
  graph_traits<Graph>::out_edge_iterator ed, ed_end;
  bool u_exists, v_exists, inserted;

  tie(u, u_exists) = GetNodeByIP(source);
  tie(v, v_exists) = GetNodeByIP(dest);

  // Both the source and target nodes SHOULD  exist
  // (otherwise, AddNode() should have been previously called)
  // Note that the neighborhood graph contains only 1-hop neighbor nodes
  // with respect to the node in question
  if (!(u_exists && v_exists))
    return false;

  // ----- ADD A PARALLEL EDGE -----
  // If both nodes exist, create a new edge
  tie(e, inserted) = add_edge(u, v, G);
  if (inserted){
    G[e].Weight = weight;
    G[e].Toc = Tic; // set timer to current time
  }
  
  return inserted;
}

////////
template <typename NeighborList>
bool TCDatabaseManager::AddNeighborhood(string ip, NeighborList& ip_list)
{
  std::vector<double> w_list(ip_list.size());
  std::vector<double>::iterator iter;

  for (unsigned int i = 0; i < w_list.size(); ++i){
    w_list[i] = -1.0;
  }

  return AddNeighborhood(ip, ip_list, w_list);
}

////////
template <typename NeighborList, typename WeightList>
bool TCDatabaseManager::AddNeighborhood(string ip,
					NeighborList& ip_list,
					WeightList& w_list)
{
  graph_traits<Graph>::vertex_descriptor u, v;
  graph_traits<Graph>::edge_descriptor e;
  typename NeighborList::iterator si;
  typename WeightList::iterator wi;
  bool exist;

  tie(v, exist) = GetNodeByIP(ip);
  if (!exist)
    return false;
  
  clear_in_edges(v, G);

  // Add new neighborhood edges for node u
  wi = w_list.begin();
  for (si = ip_list.begin(); si != ip_list.end(); ++si, ++wi){
    tie(u, exist) = GetNodeByIP(*si);
    if (exist){
      AddEdge(*si, ip, *wi);
    }
  }
  return true;
}

////////
int TCDatabaseManager::GetNumberOfNeighbors(string ip)
{
  bool exist;
  std::list<string> ip_list;

  exist = GetNeighborhood(ip, ip_list);

  if (exist)
    return ip_list.size();
  else
    return -1;
}

////////
int TCDatabaseManager::GetNumberOfNeighbors(int index)
{
  string ip, mac;
  bool tpc, exist;
  int max_power;

  exist = GetNodeInfo(index, ip, mac, tpc, max_power);

  if (exist)
    return GetNumberOfNeighbors(ip);
  else
    return -1;
}

////////
template <typename NeighborList>
bool TCDatabaseManager::GetNeighborhood(string ip, NeighborList& ip_list)
{
  std::list<double> w_list;

  return GetNeighborhood(ip, ip_list, w_list);
}

////////
template <typename NeighborList, typename WeightList>
bool TCDatabaseManager::GetNeighborhood(string ip,
					NeighborList& ip_list,
					WeightList& w_list)
{
  graph_traits<Graph>::vertex_descriptor u, v;
  graph_traits<Graph>::in_edge_iterator ed, ed_end;
  typename NeighborList::iterator si;
  bool exist;

  tie(v, exist) = GetNodeByIP(ip);
  if (!exist)
    return false;

  ip_list.clear();
  w_list.clear();

  // Loop over all in-edges, get the source nodes (neighbors),
  // and build a unique neighbor list
  for (tie(ed, ed_end) = in_edges(v, G); ed != ed_end; ++ed){
    u = source(*ed, G);

    // Add node and weight to the respective lists if node is unique
    si = find(ip_list.begin(), ip_list.end(), G[u].IP);
    if (si == ip_list.end()){
      ip_list.push_back(G[u].IP);
      w_list.push_back(G[*ed].Weight);
    }
  }
  return true;
}


////////
bool TCDatabaseManager::GetNodeInfo(int index, string& ip, string& mac,
				   bool& tpc, int& max_power)
{
  graph_traits<Graph>::vertex_descriptor v;

  if (index >= NumberOfNodes())
    return false;

  v = vertex(index, G);

  ip = G[v].IP;
  mac = G[v].MAC;
  tpc = G[v].TPC;
  max_power = G[v].MAX_POWER;

  return true;
}

////////
bool TCDatabaseManager::GetNodeInfo(string source_ip, string& ip, string& mac,
				   bool& tpc, int& max_power)
{
  graph_traits<Graph>::vertex_descriptor v;
  bool exist;

  tie(v, exist) = GetNodeByIP(source_ip);
  if (!exist)
    return false;

  ip = G[v].IP;
  mac = G[v].MAC;
  tpc = G[v].TPC;
  max_power = G[v].MAX_POWER;

  return true;
}

/////////
void TCDatabaseManager::PrintGraph()
{
  graph_traits<Graph>::vertex_iterator vi, vi_end;
  graph_traits<Graph>::edge_iterator ed, ed_end;

  Graph GG;
  GetGraph(GG);

  std::cout << std::endl << "vertices(GG)" << std::endl;
  std::cout <<              "------------" << std::endl;
  
  for (tie(vi, vi_end) = vertices(GG); vi != vi_end; ++vi){
    std::cout << GG[*vi].IP << " ; ";
    std::cout << GG[*vi].MAC << " ; ";
    std::cout << "TPC: " << (GG[*vi].TPC ? "yes" : " no") << " ; ";
    std::cout << "Max_Power: " << GG[*vi].MAX_POWER << " dBm" << " ; ";
    std::cout << "Time-out in " << (T - (Tic - GG[*vi].Toc)) << " sec";
    std::cout << std::endl;
  }
  std::cout << std::endl;

  std::cout << "  edges(GG)  " << std::endl;
  std::cout << "-------------" << std::endl;

  graph_traits<Graph>::vertex_descriptor u, v;

  for (tie(ed, ed_end) = edges(GG); ed != ed_end; ++ed){
    u = source(*ed, GG);
    v = target(*ed, GG);
    std::cout << "Weight(" << GG[u].IP << " , " << GG[v].IP << ") = ";
    std::cout << GG[*ed].Weight << " ; ";
    std::cout << "Time-out in " << (T - (Tic - GG[*ed].Toc)) << " sec";
    std::cout << std::endl;
  }
  std::cout << std::endl;

/*
  std::cout << std::endl;
  std::cout << "  edges(G)  " << std::endl;
  std::cout << "------------" << std::endl;

  for (tie(ed, ed_end) = edges(G); ed != ed_end; ++ed){
    u = source(*ed, G);
    v = target(*ed, G);
    std::cout << "Weight(" << G[u].IP << " , " << G[v].IP << ") = ";
    std::cout << G[*ed].Weight << " ; ";
    std::cout << "Time-out in " << (T - (Tic - G[*ed].Toc)) << " sec";
    std::cout << std::endl;
  }
  std::cout << std::endl;
*/

}

/////////
bool TCDatabaseManager::GetGraph(Graph& GG)
{
  // The graph must be ready in order to be copied
  if (CheckGraph() == false)
    return false;

  MakeSimpleGraph(GG);

  return true;
}

/////////
void TCDatabaseManager::MakeSimpleGraph(Graph& GG)
{
  typedef graph_traits<Graph>::vertex_descriptor node_t;
  node_t u, v, self;
  graph_traits<Graph>::vertex_iterator vi, vi_end;
  typedef graph_traits<Graph>::edge_descriptor edge_t;
  edge_t e;
  graph_traits<Graph>::edge_iterator ed, ed_end;
  std::map<node_t, node_t> G2GG;
//  std::map<edge_t, int, compare_edge> e_counter;
//  std::map<edge_t, int, compare_edge>::iterator e_iter;
  std::map<pair<node_t, node_t>, int> e_counter;
  std::map<pair<node_t, node_t>, int>::iterator e_iter;
  bool exist;

  GG.clear(); // remove all nodes and edges from the target graph

  // Create GG's node list and initialize the node map G2GG
  tie(vi, vi_end) = vertices(G);
  self = *vi; // let self be the first node in G (i.e., self)
  for ( ; vi != vi_end; ++vi){
    u = add_vertex(GG);
    G2GG[*vi] = u;

    GG[u].IP = G[*vi].IP;
    GG[u].MAC = G[*vi].MAC;
    GG[u].TPC = G[*vi].TPC;
    GG[u].MAX_POWER = G[*vi].MAX_POWER;
    GG[u].Toc = G[*vi].Toc;
  }

  // Loop over all edges in G and add edges to GG
  for (tie(ed, ed_end) = edges(G); ed != ed_end; ++ed){
    // Disregard edges that are outside the time-averaging window
    if ( (Tic - G[*ed].Toc) > T_e ){
      continue;
    }

    u = source(*ed, G); // note: u is in G
    v = target(*ed, G); // note: v is in G

    tie(e, exist) = edge(G2GG[u], G2GG[v], GG);

    if (!exist){ // if edge e does NOT already exist in GG, add it
      tie(e, exist) = add_edge(G2GG[u], G2GG[v], GG); // note: e is in GG !!!
      GG[e].Weight = G[*ed].Weight;
      GG[e].Toc = G[*ed].Toc;

      // If the target node is self, use averaging over the time-window
      if ( (self == v) && useAvg ){
        e_counter[make_pair(G2GG[u], G2GG[v])] = 1;
      }
      else{ // otherwise, simply flag the edge with a value of 0
        e_counter[make_pair(G2GG[u], G2GG[v])] = 0;
      }
    }
    else{ // if edge e exists in GG...
      // If the target node is self, use averaging over the time-window
      if ( (self == v) && useAvg ){
        e_counter[make_pair(G2GG[u], G2GG[v])] += 1;
        GG[e].Weight += G[*ed].Weight;
        // If the edge is more recent (larger Toc), also update Toc value
        if ( G[*ed].Toc > GG[e].Toc ){
          GG[e].Toc = G[*ed].Toc;
        }
      }
      else{ // If the target node is NOT self, do NOT use averaging
        // If the edge is more recent (larger Toc), simply update the edge
        if ( G[*ed].Toc > GG[e].Toc ){
          GG[e].Toc = G[*ed].Toc;
          GG[e].Weight = G[*ed].Weight;
        }
      }
    }
  }

  // Perform averaging based on the edge count for parallel edges
  // Note that e_counter[] == 0 indicates an edge that should not be averaged
  if (useAvg){
    for (e_iter = e_counter.begin(); e_iter != e_counter.end(); ++e_iter){
      int count = (*e_iter).second;
      u = ((*e_iter).first).first;  // u is in GG
      v = ((*e_iter).first).second; // v is in GG
      tie(e, exist) = edge(u, v, GG);

      // Average only those edges that have not been flagged
      if ( count > 0){ 
        // If there aren't as many edges in the window as there should be
        // (due to lost packets), account for each lost packet by adding TC_DB_MAX_W
        if (count < N_e){
          GG[e].Weight += (N_e - e_counter[make_pair(u,v)]) * TC_DB_MAX_W;
        }

        // Average over as many samples as there are in the window
        // (the minimum is N_e though)
        int N = (count > N_e) ? count : N_e;
//        int N = count;
        GG[e].Weight = (1.0 / N) * GG[e].Weight;
      }
    }
  }
}

/////////
bool TCDatabaseManager::CheckGraph()
{
  graph_traits<Graph>::edge_iterator ed, ed_end;

  tie(ed, ed_end) = edges(G);

  // The graph is not ready if there are no edges
  if (ed == ed_end){
    isReady = false;
    return false;
  }

  // It is also not ready if at least one edge
  // does not have a valid weight value
  for (; ed != ed_end; ++ed){
    if (G[*ed].Weight < 0){
      isReady = false;
      return false;
    }
  }

  isReady = true;
  return true;
}

////////
std::pair<graph_traits<Graph>::vertex_descriptor, bool>
TCDatabaseManager::GetNodeByIP(string ip)
{
  graph_traits<Graph>::vertex_iterator vi, vi_end;
  graph_traits<Graph>::vertex_descriptor v;
  std::pair<graph_traits<Graph>::vertex_descriptor, bool> p;

  p.second = false;

  for (tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi){
    v = *vi;
    if (G[v].IP == ip){
      p.first = v; p.second = true;
      return p;
    }
  }

  p.first = *vi_end;
  return p;
}

/////////
bool TCDatabaseManager::RemoveNodeByIP(string ip)
{
  graph_traits<Graph>::vertex_descriptor v;
  bool exist;

  tie(v, exist) = GetNodeByIP(ip);

  if (exist){
    RemoveNode(v);
    return true;
  }

  return false;
}

//////////
void TCDatabaseManager::ResetNodeTimer(graph_traits<Graph>::vertex_descriptor v)
{
  G[v].Toc = Tic;
}

//////////
void TCDatabaseManager::RemoveNode(graph_traits<Graph>::vertex_descriptor v)
{
  clear_vertex(v, G); // Remove all edges to and from vertex v
  remove_vertex(v, G); // Remove vertex v from the vertex set of the graph
}


//////////
void TCDatabaseManager::RemoveEdge(graph_traits<Graph>::edge_descriptor e)
{
  remove_edge(e, G); // Remove edge e from the edge set of the graph
                     // Note that this function is multigraph compatible
}

/////////
void TCDatabaseManager::UpdateGraph()
{
  graph_traits<Graph>::vertex_iterator vi, vi_end;
  graph_traits<Graph>::edge_iterator ed, ed_end;

  // Find nodes whose timers have expired and remove them from the Graph
  tie(vi, vi_end) = vertices(G);
  
  // Reset timer for the first node (the root node's timer should never expire)
  ResetNodeTimer(*vi);

  while (vi != vi_end){
    if ( (Tic - G[*vi].Toc) > T ){
      RemoveNode(*vi);
      tie(vi, vi_end) = vertices(G);
      continue;
    }
    ++vi;
  }

  // Remove edges whose timers have expired
  for (tie(ed, ed_end) = edges(G); ed != ed_end; ++ed){
    if ( (Tic - G[*ed].Toc) > T_e){
      RemoveEdge(*ed);
    }
  }
}

#endif // TC_DB_MANAGER_HPP
